1. Technical Field
This invention relates in general to semiconductor chip design techniques, and more particularly, to techniques for optimizing the physical order of macros within a vertical or horizontal data-path stack to be incorporated in a semiconductor chip.
2. Description of the Prior Art
Data-path chips (e.g., microprocessors) are implemented using a combination of data-path logic, control logic and memory arrays. Data-path logic is conventionally laid out in the form of bit stacks, see, e.g., J. Crawford, "Architecture of the Intel 80386," Proceedings IEEE ICCD, pp. 154-160, October 1986; and Dupont et al., "ROMP/MMU Circuit Technology and Chip Design," IBM RT Personal Computer Technology, SA23-1057, pp. 66-71, 1986. A bit-stack (or stack) is made up of data-path macros, such as registers, adders, shifters, multiplexers, buffers, etc. The data-path macros are stacked up vertically (or horizontally) and wired almost exclusively with vertical (horizontal) wires or buses. (In the optimizing technique described herein, an assumption is made that a vertical stack is to be ordered. However, the inventive technique is equally applicable to horizontal data-path stacks.)
Data flow information is processed along the bit-aligned data-path pipelines. The operation of the data-path macros is controlled by the control logic (or random logic) implemented in the form of standard cells. Large memory arrays (cache, register file) and special purpose, predesigned macros are also used as required. A data-path chip is typically made up of a mixture of different types of objects (or blocks): hundreds of data-path macros (30-75% chip area), thousands of small control logic cells (25-50% chip area), and some contain a few large macros such as memory array (0-30% chip area). It is not uncommon for the data-path logic to require more than one data-path stack in layout, e.g., see FIG. 1.
As noted, the present technique is directed to optimizing the physical ordering of macros within each data-path stack to be incorporated in a chip. Most, if not all, prior art block placement techniques (which typically operate in two-dimensions) fail to provide an optimal physical ordering of macros for a one-dimensional stack. Failure to optimize macro ordering can create significant problems for chip design. Each bit of a stack macro has a predefined number of physical wiring channels capable of accepting macro buses, i.e., predetermined physical connections between selected macros of the stack. To wire a stack within its physical boundaries requires that the number of buses wiring through each bit be less than or equal to the number of available wiring channels through the bit. As explained further herein, if a particular macro has an insufficient number of wiring channels per bit to accommodate another bus, then the bus must exit and thereafter re-enter the stack to wire around the congestion. In such a case, the stack grows by the equation:
2.times.NumNetsInBus.times.WidthInMicrons PA1 NumNetsInBus=number of wires in the bus; PA1 WidthInMicrons=width in microns of one wire in combination with a corresponding space between wires.
wherein:
In addition, optimally decreasing the number of wiring channels per bit needed to accommodate the required bus interconnections provides a chip designer with flexibility to embed global wiring within the stack. In addition, if the required number of wiring channels is reduced, then each bit's width can be physically designed smaller resulting in an overall narrower stack width. Also, optimizing the order of stack macros shrinks the length of bus wires which correspondingly reduces the wiring capacitance thereby increasing chip performance.
Two processor based two-dimensional design techniques discussed in the open literature are CPLACE and MSMO, e.g., see Villarrubia et al., "IBM RISC Chip Design Methodology," IBM Advanced Workshop Division, ICCD-89 Conference, pp. 143-147; and Luk, "Multi-Terrain Partitioning and Floor-Planning for Data-Path Chip (Microprocessor) Layout," 26 ACM/IEEE Design Automation Conference, pp. 110-115, June 1989, respectively. CPLACE is a min-cut based placement program that utilizes ordered gain. This technique divides a stack of macros in half and then proceeds to redistribute macros between the two halves in an effort to minimize the number of connections therebetween. The process is continued until a minimum number of connections is found to cross each boundary. In MSMO processing, a number of potential terrain configurations are evaluated and the floor plan that provides the shortest length and smallest overflow in global wires, as well as meeting the timing and size requirements, is selected.
By way of comparative example, a main bit stack of 139 macros, 157 buses with 13,664 I/O connections was examined. Starting from a random order of stack macros, MSMO processing required 17 wiring channels per bit, while CPLACE needed 15 wiring channels per bit. Neither approach is believed to have produced an optimum, nor even an acceptable configuration (e.g., 12-14 wiring channels per bit). Time consuming manual redesign of the final MSMO or CPLACE generated bit stack configuration would be necessary to attain such an optimal ordering. This procedure is obviously cumbersome, particularly since during actual chip design the macros comprising a data-bit stack typically change numerous times before a final design is found acceptable. At each iteration it may be necessary for the chip designer to know specific characteristics of the proposed data-path stack, including the minimum number of wiring channels per bit required for internal wiring of the stack.
A genuine need thus exists in the semiconductor chip design art for an automated ordering technique capable of optimizing the physical order of stack macros to a greater extent than pre-existing techniques, and in a more efficient manner without the need for manual reordering of the stack to achieve an acceptable number of wiring channels per bit.